<?php
/*
剑指 Offer 13. 机器人的运动范围
地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。
一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。
例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。
但它不能进入方格 [35, 38]，因为3+5+3+8=19。
请问该机器人能够到达多少个格子？

示例 1：
输入：m = 2, n = 3, k = 1
输出：3

示例 2：
输入：m = 3, n = 1, k = 0
输出：1

提示：
1 <= n,m <= 100
0 <= k <= 20

难度：中等

https://leetcode.cn/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/


*/

$m   = 2;
$n   = 3;
$k   = 1;
$m   = 1;
$n   = 2;
$k   = 1;
$obj = new Code_Offer13();
var_dump($obj->main($m, $n, $k));

class Code_Offer13
{

    // 数字的每一位上的数字相加和
    protected function _digitSum($num)
    {
        $res = 0;
        while ($num) {
            $res += $num % 10;
            $num = intval($num / 10);
        }
        return $res;
    }

    public function main($m, $n, $k)
    {
        if ($k == 0) {
            //0 + 0 = 0 符合题意直接返回
            return 1;
        }
        $visited = [];
        return $this->_dfs(0, 0, $k, $m, $n, $visited);
    }

    /** 用&引用代替形参，实现指针传递，减少多余的内存申请释放过程所消耗的时间 */
    protected function _dfs($x, $y, $k, $m, $n, &$visited)
    {
        if ($this->_getRowColumnSum($x, $y) > $k) {
            return 0;
        }

        //当前位置符合条件累加一步
        $sum = 1;
        //当前的位置标记为true，即为走过
        $visited[$x][$y] = true;

        //先进行下一步位置范围准确性检测再进行搜索，减少不必要的函数调用。
        if (($tmpX = $x + 1) < $m && !$visited[$tmpX][$y]) {
            $sum += $this->_dfs($tmpX, $y, $k, $m, $n, $visited);
        }

        if (($tmpY = $y + 1) < $n && !$visited[$x][$tmpY]) {
            $sum += $this->_dfs($x, $tmpY, $k, $m, $n, $visited);
        }
        //返回自身加上从右边以及下边开始搜索到的总和
        return $sum;
    }

    protected function _getRowColumnSum($x, $y)
    {
        return $this->_digitSum($x) + $this->_digitSum($y);
    }


}